1. Field of the Invention
The present invention relates to a data classifying method, a multi-dimensional interpolation device, a multi-dimensional interpolation method, and a computer program, which are particularly suitably used for executing interpolation of N-dimensional vector signals.
2. Description of the Related Art
Recently, a scanner, a video camera, etc. have been widely used as input units. Various types of color printers utilizing ink jets, dye sublimation, electrophotography, etc. have been widely used as output units. Those color input and output units have specific color spaces. Accordingly, for example, when a color image obtained with a certain scanner is directly transferred to and printed by a certain color printer, colors of a printed color image hardly match with the colors of the original color image read by the scanner.
Overcoming such a problem with color reproduction between devices handling a color image or the like requires processing (called “color space conversion”) for converting a color space of the input unit to a color space of the output unit. To increase a color reproduction capability between the input unit and the output unit, each of the input unit and the output unit includes the color-space conversion function.
The term “color space conversion” practically means the whole of a series of image processing steps, such as input γ correction, luminance density conversion, masking, black generation, UCR (under color removal), output γ correction, etc., or some of those steps. In general, digital image signals of three colors (e.g., red, green and blue that are abbreviated to “RGB” hereinafter) used in the input unit are read at the same time and are converted to digital image signals of three colors (e.g., cyan, magenta and yellow that are abbreviated to “CMY” hereinafter) or four colors (e.g., cyan, magenta, yellow and black that are abbreviated to “CMYK” hereinafter) used in the output unit. Also, in the case of an electrophotographic copying machine, because a printer's engine characteristics are changed with the lapse of operation time, periodic calibration is required. In that case, conversion of four colors (e.g., “CMYK”) in the input unit to four colors (e.g., “CMYK”) in the output unit is also required.
A first known technique for realizing the above-mentioned color-space converting process is disclosed in U.S. Pat. No. 4,837,722. According to the first known technique, the three-dimensional cubic (tri-linear) interpolation method or the three-dimensional tetrahedron interpolation method is executed at a high speed through the steps of divisionally storing a 3D-LUT (three-dimensional lookup table), which stores the results of the color conversion, in eight memories, and reading reference values from the 3D-LUT in parallel.
With the disclosed technique, the reference values corresponding to respective apexes of a unit hypercube and used for interpolation are all stored in different memories from one another so that access conflicts will not occur when the reference values are read out of the memories. Also, the 3D-LUT is stored in eight memories while being evenly divided without overlaps (when a multi-dimensional LUT is so divisionally stored in a plurality of memories in order to read reference values from the multi-dimensional LUT in parallel, the plurality of memories will be referred to as “sub-memories” hereinafter). The description of the first known technique is limited to the three-dimensional interpolation method. However, when multi-dimensional interpolation processing is executed by using the first known technique, the processing can be executed by divisionally storing the multi-dimensional LUT in a number 2N of sub-memories.
Also, there is a second known technique that executes the three-dimensional tetrahedron interpolation method at a high speed through the steps of storing a 3D-LUT in four sub-memories while dividing it without overlaps, and reading reference values in parallel (see Japanese Patent Laid-Open No. 10-307911).
With the second known technique, when executing the three-dimensional tetrahedron interpolation method, four reference values corresponding to respective apexes of a selected tetrahedron are read in parallel to increase the speed of the interpolation processing. Further, in the second known technique, the 3D-LUT is stored in four sub-memories while being evenly divided without overlaps so that access conflict will not occur when the reference values are read out of the sub-memories, as in the first known technique.
In addition, the LUT in the second known technique is divided in the multi-dimensional form. Accordingly, when the hyper-tetrahedron ((N+1)-hedron) interpolation method with N-dimensional inputs is executed, a multi-dimensional (N-dimensional) LUT can be divisionally stored in a number (N+1) of sub-memories.
Thus, the second known technique is superior to the first known technique in point of using a smaller number of sub-memories.
According to the first known technique, the multi-dimensional LUT is divided into 2N by storing a number N of reference values corresponding to respective apexes of a unit hypercube in a number N of sub-memories. Therefore, the first known technique is advantageous in that it can also be realized by using other methods (e.g., the three-dimensional cubic (tri-linear) interpolation method and the three-dimensional triangular-prism (prism) interpolation method) other than the multi-dimensional tetrahedron interpolation method.
However, when the first known technique is practiced on the premise of using the multi-dimensional tetrahedron interpolation method, a number 2N of memory peripheral circuits, such as memory interfaces, are required to read a number (N+1) of reference values necessary for the interpolation processing from the sub-memories in parallel. Consequently, redundant circuits are increased.
According to the second known technique, the processing is limited only to the multi-dimensional tetrahedron interpolation method, and the multi-dimensional (N-dimensional) LUT is divisionally stored in a minimum number (N+1) of sub-memories. Hence, the second known technique is advantageous in that memory peripheral circuits are also constituted in an optimum scale.
However, when N is not a value of (second power−1), the number of sub-memories is not a value of second power. For example, when N is 4, the number of sub-memories is 5. Then, when the second known technique is practiced in the form of hardware, the processing cannot be handled in binary mode. For that reason, in the case of N being not a value of (second power−1), a divider is required to generate addresses for accessing the sub-memories because the addresses cannot be generated with only shift operation and bit masking. In addition, memories are generally manufactured as products having a word number of second power. Therefore, when the sub-memories are constituted using marketed memories, the second known technique necessitates the use of memories each having a redundant word number.